#include <iostream>
#include <stack>

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
};

// 迭代的方法，找到第三小的节点就停下
int kthSmallest(TreeNode *root, int k)
{
    std::stack<TreeNode *> st;
    while (root != nullptr || st.size() != 0)
    {
        // 将root节点以及左节点全部放入st
        while (root != nullptr)
        {
            st.push(root);
            root = root->left;
        }
        // 释放栈顶元素
        root = st.top();
        st.pop();
        k--;
        if (k == 0)
            break;
        root = root->right;
    }
    return root->val;
}

// 最小的元素所在的位置是最左端，第二小的节点在最左端有右节点的节点的最左端
// 所以先移除最小的元素，之后如果有右节点，那么第二小的就在右节点的最左端，如果没有的话，那么该节点的父亲就是最小值。